#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 003. 无重复字符的最长子串.py
@time: 2022/1/5 13:41
@desc: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
> 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

@解题思路：
    1. 设双指针
    2. 左指针负责控制字符区间长度（也就是在区间左边往右移动）
    3. 右指针负责不断纳入非重复字符串（也就是固定了左指针后试图不断右移）
    4. t: O(n), s: O(涉及字符数)
@涉及面经：
    1. https://www.nowcoder.com/discuss/tiny/831515?channel=666&source_id=feed_index_nctrack&fromIframe=true
'''
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 用来存放目前没有重复的字符串
        occ = set()
        n = len(s)
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针移动
                # 移除i的前一个元素，也就是缩短区间
                occ.remove(s[i - 1])
            # rk一直右移并将非重复字符加入到集合中，遇到重复的则退出
            while rk + 1 < n and not s[rk + 1] in occ:
                # 当右指针所指的新元素不在集合里，则可以加入
                occ.add(s[rk + 1])
                rk += 1

            # 当碰到重复的时候跳出了上面的循环，计算最长的无重复字符串长度，并进将左指针右移，进入下一轮循环
            ans = max(ans, rk - i + 1)

        return ans

# 变量名好看点
class Solution2(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        occ = set()
        n = len(s)
        right, ans = -1, 0
        for left in range(n):
            if not left==0:
                # 缩短区间， 移动左指针
                occ.remove(s[left-1])
            while right+1<n and s[right+1] not in occ:
                # 当右指针下一个元素不重复时，就可以扩大向右区间
                right += 1
                occ.add(s[right])
            # 遇到重复的或者越界了就会来到本句，此时计算最大值，目前区间长度为right-left+1
            ans = max(ans, right-left+1)
        return ans